package qsc.algorithm.primAlgorithm;

/**
 * @auther QiuShangcheng
 * @create 2021/4/21
 */
public class PrimAlgorithm {


    /**
     *  普利姆算法实现
     * @param mGraph 图
     * @param v 起始节点
     */
    public static void primAlgorithm(MGraph mGraph,int v) {
        //存储被记录过的节点
        int[] visits = new int[mGraph.getVerxs()];
        //将起始点v置位已记录
        visits[v] = 1;
        //记录一条边的两端节点
        int h1 = -1;
        int h2 = -1;
        //记录以上描述边的权值
        int minWeight = 10000;
        //n个节点最少需要n-1条边，因此最小生成树应为n-1条边，需要执行n-1次获取每次最小边
        for (int i = 1; i < mGraph.getVerxs(); i++) {

            //获取一次相邻边的最小权值
            for (int j = 0; j < mGraph.getVerxs(); j++) {
                for (int k = 0; k < mGraph.getVerxs(); k++) {
                    //判断当前边为已记录节点的邻近边，并且当前边的权值应小于记录的最小值
                    if (visits[j] == 1 && visits[k] == 0 && mGraph.getWeight()[j][k] < minWeight) {
                        minWeight = mGraph.getWeight()[j][k];
                        h1 = j;
                        h2 = k;
                    }
                }
            }

            //将该节点置位已记录节点
            visits[h2] = 1;
            System.out.println("边<" + mGraph.getData()[h1] + "," + mGraph.getData()[h2] + "> 权值:" + minWeight);
            //将最小权值重置
            minWeight = 10000;
        }
    }
}
